#pragma once
#include <iostream>
#include <vector>
using namespace std;
enum State
{
	EMPTY,
	EXIST,
	DELETE
};

template<class K, class V>
struct HashDate
{
	pair<K, V> _kv;
	State _state = EMPTY;
};

template<class K, class V>
class closehash
{
public:
	bool insert(const pair<K, V>& kv)
	{
		if (find(kv.first)) return false;
		if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7)
		{
			size_t new_size = _tables.size() == 0 ? 10 : _tables.size() * 2;
			closehash<K, V> new_ch;
			new_ch._tables.resize(new_size);
			for (auto& t : _tables)
			{
				if (t._state == EXIST)
				{
					new_ch.insert(t._kv);
				}
			}
			_tables.swap(new_ch._tables);
		}
		size_t hashi = kv.first % _tables.size();
		while (_tables[hashi]._state == EXIST)
		{
			hashi++;
			hashi %= _tables.size();
		}
		_tables[hashi]._kv = kv;
		_tables[hashi]._state = EXIST;
		_n++;
		return true;
	}

	HashDate<K, V>* find(const K& key)
	{
		if (_tables.size() == 0) return nullptr;
		size_t hashi = key % _tables.size();
		while (_tables[hashi]._state != EMPTY)
		{
			if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key)
				return &_tables[hashi];
			hashi++;
			hashi %= _tables.size();
		}
		return nullptr;
	}
	bool erase(const K& key)
	{
		HashDate<K, V>* ret = find(key);
		if (ret)
		{
			ret->_state = DELETE;
			--_n;
			return true;
		}
		else
		{
			return false;
		}
	}
private:
	size_t _n = 0;
	vector<HashDate<K, V>> _tables;
};

